#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

dp[m][n] : 以[m][n]结尾的最长相同元素
dp[m][n] = max(
    0,                      # not equal
    1 + dp[m-1][n-1]        # if A[m] == B[n]
    )
"""


class Solution:
    """
    连续子串
    """
    def longestCommonSubstring(self, A, B):
        if not A or not B:
            return 0

        self.A = A
        self.B = B

        len_a = len(A)
        len_b = len(B)

        self.record = self.make_matrix(len_a+1, len_b+1, 0)
        self.max_cnt = 0
        self.max_idxs = []

        self.longest_of_index(A, B)
        return self.max_cnt

    def longest_of_index(self, A, B):
        print(A, B)
        for idx_a in range(1, len(A)+1):
            for idx_b in range(1, len(B)+1):
                # print('here')
                if A[idx_a-1] == B[idx_b-1]:
                    v = self.record[idx_a-1][idx_b-1] + 1
                    print('match')
                else:
                    # print('no match')
                    v = 0
                if v > self.max_cnt:
                    self.max_idxs = [(idx_a, idx_b)]
                    self.max_cnt = v
                elif v == self.max_cnt:
                    self.max_idxs.append((idx_a, idx_b))

                self.record[idx_a][idx_b] = v


    def make_matrix(self, rows, cols, init_v=None):
        one_row = [init_v] * cols
        matrix = [list(one_row) for i in range(rows)]
        return matrix

    def get_all_common_substrings(self):
        result = []
        for idx_a, idx_b in self.max_idxs:
            s = self.get_one_common_substring(idx_a, idx_b)
            result.append(s)

        return result

    def get_one_common_substring(self, idx_a, idx_b):
        s = ''
        while self.record[idx_a][idx_b]:
            assert self.A[idx_a-1] == self.B[idx_b-1]
            s = self.A[idx_a-1] + s
            idx_a -= 1
            idx_b -= 1

        return s



def main():
    print("start main")
    s = Solution()
    ret = s.longestCommonSubstring("abcdefg", "cdefg")
    print(s.max_idxs)
    print(ret)

    com_s = s.get_all_common_substrings()
    print(com_s)

if __name__ == "__main__":
    main()
